package com.lry.basic.algorithm.recursion;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class CombinationSum {

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        if(null==candidates||candidates.length==0)
            return ans;
        Arrays.sort(candidates);
        List<Integer> path = new ArrayList<>();

        dfs(0,0,target,candidates,path,ans);

        return ans;
    }

    private void dfs(int start,int sum,int target , int[] candidates, List<Integer> path, List<List<Integer>> ans) {
        if(sum==target){
            ans.add(new ArrayList<>(path));
            return;
        }

        for(int i=start;i<candidates.length;i++){
            if(sum+candidates[i]>target){
                break;
            }
            sum+=candidates[i];
            path.add(candidates[i]);

            dfs(i,sum,target,candidates,path,ans);

            sum-=candidates[i];
            path.remove(path.size()-1);
        }
    }


    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        if(null==candidates||candidates.length==0)
            return ans;
        Arrays.sort(candidates);
        List<Integer> path = new ArrayList<>();

        dfs2(0,0,target,candidates,path,ans);

        return ans;
    }

    private void dfs2(int start, int sum, int target, int[] candidates, List<Integer> path, List<List<Integer>> ans) {
        if(sum==target){
            ans.add(new ArrayList<>(path));
            return;
        }

        for(int i=start;i<candidates.length;i++){
            if(sum+candidates[i]>target){
                break;
            }
            if(i>start&&candidates[i]==candidates[i-1]){
                continue;
            }
            sum+=candidates[i];
            path.add(candidates[i]);

            dfs2(i+1,sum,target,candidates,path,ans);

            sum-=candidates[i];
            path.remove(path.size()-1);
        }
    }


    public static void main(String[] args) {
        System.out.println(new CombinationSum().combinationSum(new int[]{8,7,4,3}, 11));
        System.out.println(new CombinationSum().combinationSum2(new int[]{1, 1,2,5,6,7}, 8));
    }
}
